/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 /**
  * Note: The returned array must be malloced, assume caller calls free().
  */

typedef struct TreeNode TreeNode;

int Count_Tree_Node(TreeNode* root)
{
    if (!root)
        return 0;

    return 1 + Count_Tree_Node(root->left) + Count_Tree_Node(root->right);
}

void Preorder(TreeNode* root, int* arr, int* i)
{
    if (!root)
        return;
    arr[*i] = root->val;
    (*i)++;

    Preorder(root->left, arr, i);
    Preorder(root->right, arr, i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int* arr = (int*)malloc(110 * 4);

    int i = 0;
    Preorder(root, arr, &i);

    *returnSize = Count_Tree_Node(root);

    return arr;
}